#pragma once

/// 结点结构
template <typename E>
struct LNode
{
    E data;      // 数据域
    LNode *next; // 指针域
};

/// 链表类型
// typedef LNode *LinkList; // for C
template <typename E>
using LinkList = LNode<E> *; // for C++11

/// 初始化链表为空表 InitList(&L)
template <typename E>
void InitList(LinkList<E> &L)
{
    L = new LNode<E>;
    L->next = nullptr;
}

/// 链表插入 ListInsert(&L, i, e)
template <typename E>
void ListInsert(LinkList<E> &L, int i, E e)
{
    // 查找第 i-1 个结点 p
    auto p = L;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        ++j;
    }

    // 若 p 存在，在其后插入 e
    if (p && j == i - 1) {
        // 新建结点 s，保存 e
        auto s = new LNode<E>;
        s->data = e;
        // 在 p 之后插入 s
        s->next = p->next;
        p->next = s;
    } else {
        throw "Invalid i";
    }
}

/// 链表删除 ListDelete(&L, i, &e)
template <typename E>
void ListDelete(LinkList<E> &L, int i, E &e)
{
    // 查找第 i-1 个结点 p
    auto p = L;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        ++j;
    }

    // 若第 i 个结点存在，则删除
    if (p && j==i-1 && p->next) {
        // 取出数据元素，用 e 返回
        auto q = p->next;  // 指向第 i 个结点
        e = q->data;
        // 删除第 i 个结点 q
        p->next = q->next;
        delete q;
    } else {
        throw "Invalid i";
    }
}
